package com.gaogzhen.algorithm.sort;

/**
 * 归并排序
 */
public class Merge {

    private static Comparable[] assit;

    /**
     * 排序
     *
     * @param a
     */
    public static void sort(Comparable[] a) {
        // 1、初始化辅助数组
        assit = new Comparable[a.length];
        // 2、定义lo,hi，分别记录数组最小索引和最大索引
        int lo = 0;
        int hi = a.length - 1;
        // 3、调用重载sort方法完成子数组索引冲Lo到hi的排序
        sort(a, lo, hi);
    }

    /**
     * 分组和归并
     * 递归
     *
     * @param a
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] a, int lo, int hi) {
        // 递归结束条件：hi>=lo
        if (lo >= hi) {
            return;
        }
        // 1、确定分组中间量mid
        int mid = lo + (hi - lo) / 2;
        // 2、拆分子数组
        // 2.1、调用sort完成子数组索引从lo->mid的排序
        sort(a, lo, mid);
        // 2.2、调用sort完成子数组索引从mid+1->hi的排序
        sort(a, mid + 1, hi);
        // 3、有序归并
        // 3.1、完成子数组2.1和2.2的归并
        merge(a, lo, mid, hi);
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 1、初始化指针i,p1,p2
        int i = lo;
        int p1 = lo;
        int p2 = mid + 1;
        // 1.1、i为数组assit指针，p1为索引lo->mid子数组索引，p2为索引mid+1->hi子数组索引
        // 2、同时遍历2个子数组并比较，较小的存入assit,直至任意一个子数组结束
        while (p1 <= mid && p2 <= hi) {
            if (compare(a[p1], a[p2])) {
                assit[i++] = a[p2++];
            }else {
                assit[i++] = a[p1++];
            }
        }
        // 3、如果任意一个子数组有剩余，直接存入assit
        while (p1 <= mid) {
            assit[i++] = a[p1++];
        }
        while (p2 <= hi) {
            assit[i++] = a[p2++];
        }
        // 4、复制assit数组数据回数组a原位置
        for (int k = lo; k <= hi; k++) {
            a[k] = assit[k];
        }
    }

    // 比较a是否大于b
    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }
}
